Let : r.v. which values is , where = vertex chosen in the iteration of the algorithm.
Then,
Now by linearity of expectation and independence of the r.v's.
Since at each iteration we pick uniformly at random from , each vertex has to be picked.
Therefore,
